package c_困难;

/**
 * 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。  
 * 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。
 * 
 * @author hecai
 * @date 2020年5月4日
 */
public class 跳跃游戏II {
	public static void main(String[] args) {
		int[] nums = {2,3,1,1,4};
//		int[] nums = {1,2,3};
		System.out.println(jump(nums));
	}

	public static int jump(int[] nums) {
		if(nums.length == 1)
			return 0;
		int count = 0;
		int len = nums.length-1;
		int minIndex = Integer.MAX_VALUE;
		while(minIndex > 0) {
			int index = len-1;
			//从后面往前面找 找最小的可以直接到达目标的下标
			//int minIndex = Integer.MAX_VALUE;
			while(index >= 0) {
				if(nums[index] + index >= len) {
					minIndex = Math.min(minIndex, index);
				}
				index --;
			}
			len = minIndex;
			count++;
		}
		return count;
	}

}
